User blog:Googology Noob/SuperJedi's X Function
I recently stumbles upon a pretty cool uncomputable function defined by SuperJedi224. You are allowed to use digits, the successor function (Sn=n+1), addition, multiplication, exponentiation, commas, parentheses and letters of the alphabet (no ellipses!). Commas and parentheses do not count as symbols (line breaks do). X(n) is the maximal output using n symbols. Here I will post some general bounds. Bounds Here I will post some general bounds I have found. Hyperoperators The hyperoperators are very basic, and should be easy to define. Let's try! U(a,b,1)=a^b U(a,1,c)=a U(a,Sb,Sc)=U(a,U(a,b,Sc),c) That was 31 symbols. If we wanted to define a number we'd need to use 5 more symbols: O(9,9,9) and a line break. So I've proved that X(36) > f_w(9). How is that a general bound? Well, we can recurse on this system! U(a,b,1)=a^b U(a,1,c)=a U(a,Sb,Sc)=U(a,U(a,b,Sc),c) Ax=U(x,x,x) Nothing impressive. 8 more symbols to reach f_w+1(n) growth rate. U(a,b,1)=a^b U(a,1,c)=a U(a,Sb,Sc)=U(a,U(a,b,Sc),c) Ax=U(x,x,x) B0=9 BSx=ABx This may not look like much, but this builds up to a huge improvement. We used 13 more symbols to reach f_w+2(n) growth rate. Isn't that even worse than before? U(a,b,1)=a^b U(a,1,c)=a U(a,Sb,Sc)=U(a,U(a,b,Sc),c) Ax=U(x,x,x) B0=C0=9 BSx=ABx CSx=BCx Now we used 11 more symbols to reach f_w+3(n) growth rate, but from here it's easy to generalize. In general, we need to add 11 symbols for each new function: 3 symbols to make the 0th member of the function equal to 9, a line break, and 7 symbols to make it iterate the previous function. Each iteration adds +1 to the level of the function in FGH, so we have the general bound: X(31+8+13+11m+2)=X(54+11m)>f_w+m+2(9). This gives us a limit ordinal of f_w2(n). Surely we can do better! Let's try the Ackermann function. 2 arguments should be easier to define, right? Ackermann Function I'm talking about the 2 argument Peter-Rosza one, the easiest to define from scratch. A(0,y)=Sy A(Sx,0)=A(x,1) A(Sx,Sy)=A(x,A(Sx,y)) This takes only 28 symbols to reach f_w(n). The first 2 iterations take an additional 20 symbols to reach f_w+2(n), and we can change the second rule slightly for an increase in strength: A(0,y)=Sy A(Sx,0)=A(x,9) A(Sx,Sy)=A(x,A(Sx,y)) Bx=A(x,x) C0=9 CSx=BCx And from here it's the same. By how much have we improved the bound? Now X(28+20+11m+2)=X(50+11m)>f_w+m+2(9). That merely reduced our symbol count by 4. Very lame. How about some better extensions to the hyperoperators, say Conway's chained arrows. Chained arrow notation Let's define firstly the rules up to 3 entries. C(a,1,c)=a C(a,b,1)=a^b C(a,Sb,Sc)=C(a,C(a,b,Sc),c) This is identical to up arrows, and takes 31 symbols. Nothing new. Now let's define 4 entries. C(a,1,c)=a C(a,b,1)=a^b C(a,Sb,Sc)=C(a,C(a,b,Sc),c) C(a,1,c,d)=a C(a,b,1,d)=C(a,b,1) C(a,b,c,1)=C(a,b,c) C(a,b,Sc,Sd)=C(a,b,C(a,b,c,Sd),d) Despite reaching the limit of all above, that's a lot of rules. Isn't there a way to shorten that? Yes, there is! Firstly, we don't need the C(a,1,c,d)=a rule, since all 4 entry arrays will reduce to 3 entry arrays and we have specified a rule for that. Secondly, we can put a few rules in one line, like this: C(a,1,c)=a C(a,b,1)=C(a,b,1,d)=a^b C(a,Sb,Sc)=C(a,Sb,Sc,1)=C(a,C(a,b,Sc),c) C(a,b,Sc,Sd)=C(a,b,C(a,b,c,Sd),d) Much better. We only added one new rule, and we only needed to specify 2 new cases. Does this pattern hold for 5 entries? C(a,1,c)=a C(a,b,1)=C(a,b,1,d)=a^b C(a,Sb,Sc)=C(a,Sb,Sc,1)=C(a,Sb,Sc,1,e)=C(a,C(a,b,Sc),c) C(a,b,Sc,Sd)=C(a,b,Sc,Sd,1)=C(a,b,C(a,b,c,Sd),d) C(a,b,c,Sd,Se)=C(a,b,c,C(a,b,c,d,Se),e) Yes, it does. We added three cases: when the second last number is a one, when the last number is a one, and otherwise. We can show that for the first case we needed 9 symbols: the length of the chain (5) plus the 2 successor operations plus the name of the function plus the equal sign. This holds for all amount of entries>4: for the first case we need n+4 symbols, where n is the length of the chain. For the second case we need n+4 symbols as well, for the same reason. For the last rule we need firstly one symbol for the line break, n+3 symbols to write the chain, 1 more symbol for the equal sign, then n+2 symbols for the nested expression and n symbols for the rest of the expression. This adds up to 1+n+3+1+n+2+n=3n+7 symbols. Summing it all up, we need 3n+7+n+4+n+4=5n+15 symbols to extend a chained arrow expression from all of the previous functions. Therefore, X((5n+15)(n-2))>f_w^2(n). The "times n-2" part comes from the previous symbols. This can be upperbounded as X(5n^2). Can we improve this bound? Not with chained arrows. Let's move on to something much stronger and a googology classic: BEAF. BEAF Firstly, let's define 3 and 4 entry cases. B(a,b,1)=B(a,b,1,1)=a^b B(a,1,c)=B(a,1,c,d)=a B(a,Sb,Sc)=B(a,Sb,Sc,1)=B(a,B(a,b,Sc),c) B(a,Sb,1,Sd)=B(a,a,B(a,b,1,Sd),d) B(a,Sb,Sc,d)=B(a,B(a,b,Sc,d),c,d) I have skipped a few shortenings, but notice how the behavior is much more complex than chained arrows. This is because the recursion is "smarter" and more efficient in BEAF, because it is "case-sensitive": it depends on the position of the entries in the array. With 5 entries this becomes even more clear: B(a,b,1)=B(a,b,1,1)=B(a,b,1,1,1)=a^b B(a,1,c)=B(a,1,c,d)=B(a,1,c,d,e)=a B(a,Sb,Sc)=B(a,Sb,Sc,1)=B(a,B(a,b,Sc),c) B(a,Sb,1,Sd)=B(a,Sb,1,Sd,1)=B(a,a,B(a,b,1,Sd),d) B(a,Sb,Sc,d)=B(a,Sb,Sc,d,1)=B(a,B(a,b,Sc,d),c,d) B(a,Sb,1,1,Se)=B(a,a,a,B(a,b,1,1,Se),e) B(a,Sb,c,1,Se)=B(a,a,a,B(a,b,c,1,Se),e) B(a,Sb,1,Sd,e)=B(a,a,B(a,b,1,Sd,e),Sd,e) B(a,Sb,Sc,d,e)=B(a,B(a,b,Sc,d,e),c,d,e) Whew! Quite a definition! 3 entry BEAF requires 31 symbols, 4 entry BEAF requires 89 symbols, and 5 entries require about 200 symbols. I can't find a pattern, but I believe that you can define n-length BEAF in about mn^3 to mn^4 symbols for a rather small m (5-15, say). This gives us a bound of (at the absolute worst) X(n^5)>f_w^w(n). This takes far more symbols than the previous bounds, but extends it much more. Once again, can we do better? Once again, yes we can. So far, our main advancements have been array notations that apply recursion and then fall back to less arguments. This is very strong, but we need tons of rules for each new argument. Let's go to a pretty cool system, that's an extension of something we considered before: Taro's multivariable Ackermann function. Taro's multivariable Ackermann function 1 entry function is just successor operation and 2 entries is the normal Ackermann function. Let us define the 3 entry function: A(0,0,z)=Sz A(x,Sy,0)=A(x,y,9) A(Sx,0,z)=A(x,z,z) A(x,Sy,Sz)=A(x,y,A(x,Sy,z) This extended Ackermann function (which has a slightly different definition: I changed a 1 to a 9) has a growth rate of f_w^w(n), and this 3 entry function, which takes a mere 45 symbols, about half of what 4 entry BEAF takes, reaches the limit of chained arrows. That's right: half the amount of symbols than in BEAF, and the same strength. Let's try 4 entry functions: A(0,0,0,d)=Sd A(a,b,Sc,0)=A(a,b,c,9) A(a,Sb,0,d)=A(a,b,d,d) A(Sa,0,0,d)=A(a,d,0,d) A(0,0,Sc,Sd)=A(0,0,c,A(0,0,Sc,d)) A(Sa,0,c,d)=A(a,d,c,d) A(a,b,Sc,Sd)=A(a,b,c,A(a,b,Sc,d)) This is slightly harder, but way less than the 200 symbols required for the BEAF equivalent. I actually think though (but have not proven), that n entry Ackermann function requires approximately the same amount of symbols as n-1 entry BEAF, and has the same strength as n+1 entry BEAF. Definitely a better bound, by not by tons. All our functions are bounded by f_w^w(n) so far (well, barring TMs which catch up with other functions much later), which is the limit of linear arrays in most notations. Luckily for us, we have HAN. Is it possible to reach f_phi(w,0)(n) using HAN's linear arrays? I believe so and I'm working on it now. HAN - WIP Nothing to see here. Move on. FGH/HH - WIP I believe that it is possible to define the FGH in the X function (and up to w^2 it's pretty obvious how), but it remains a work in progress for now. F(0,b,c)=Sb F(Sa,1,c)=F(a,c,c) F(Sa,Sb,c)=F(a,F(Sa,b,c),F(Sa,b,c) F(n+w,b,c)=F(n+b,b,c) F(m+n*Sa,b,c)=F(m+n*a+n,b,c) F (m+n*w,b,c)=F (m+n*b,b,c) F(n+m^Sa,b,c)=F(n+m^a*b,b,c) F(n+w^w,b,c)=F(n+w^b,b,c) In about 100 symbols I've reached f_w^w(n). However, it goes beyond that. We've defined F(w^w*w,b,c)=f_w^{w+1}(n), as well as that times w = f_w^w+2(n), and so forth. This brings us up tk the limit of our notation so far, f_w^w2(n). It shouldn't be much of a problem to define up to F(w^w^w,b,c), or even up to F(w^^n,b,c) for any n. This brings us up to our new limit, e_0. Far greater, for sure, but can we increase this? I believe that a special definition of up arrows for ordinals would get us up to phi(w,0), and from there it shouldn't be a problem to reach gamma_0. I think that we can utilize the extended veblen function (to finitely many variables) to reach up to the SVO, but that's just a guess on my part and I'll think about it. H(0,b)=b H(Sa,b)=H(a,Sb) H(n+w,b)=H(n+b,b) H(n+m*w,b)=H(n+m*b,b) H(n+a^w,b)=H(n+a^b,b) So, um, wow. I just defined the Hardy Hierarchy up to e_0 in like, 50-60 symbols. Yay! More coming soon. X Function beyond the function What's interesting about the X function is that it's not only a function: it provides us with a syntax. With a syntax we can do much, much more. On starting to define HAN's linear arrays, I found that it was more complex than I thought, and far, far more interesting. With that we can do all sort of challenges. For example, what is the largest Hollomism (googolism defined by Lawrence Hollom, not necessarily in HAN) you can define in 100 symbols or less? How about the largest expression in Hyper-E? We can extend this quite a lot! I present to you the following challenges: Largest Hollomism defined in 200 symbols or less I managed to define Giaxul in 99 symbols (harder than it looks!), and if someone can tell me how to do the black text (so that everything is censored out) I will post it. I think I will do a sort of leaderboard here, which will depend on the size of the googolism and the amount of symbols. Largest Hyper-E expression What is the largest expression defined only by Hyper-E (as in, doing E{3,3,3,3}#2 where {3,3,3,3} is BEAF doesn't count) you can define in 128 symbols or less? Note: by expression I do not mean googolism. Even if it was not defined by Saiban, it still counts. Leaderboard, ordered by size of expression and symbols. Smallest amount of symbols Here are a few small challenges: 'Moser' What is the least amount of symbols you can define the Moser in? 'Graham's Number' What is the least amount of symbols you can define Graham's number in? What is the least amount of symbols you can define Hypergraham in? 'Quintgrand Faxul' What is the least amount of symbols you can define Quintgrand Faxul in? Random Other random challenges. 'Subtraction' Define subtraction (of two non-negative integers) in the least amount of symbols. M(x,0)=x M(Sx,Sy)=M(x,y) I believe this is the simplest definition possible. Too lazy to write a proof. 'Division' Define division for 2 natural numbers. 'Future?' Who knows? Post your answers in the comments. Thanks for (hopefully) reading! Category:Blog posts